class Heap {
  constructor(comparator = (a, b) => a - b, data = []) {
    // 首先是这个类的构造函数 接受两个参数,一个是构造器,默认是小顶堆,也就是递增的 可以对其进行改造,如果是对象可以斜撑a.val和b.val,第二个参数是数据 默认是一个空数组 ,也可以传入默认的数据
    this.data = data
    this.comparator = comparator //比较器
    this.heapify() //堆化函数
  }

  heapify() {
    if (this.size() < 2) return // 如果个数小于2 没必要去堆化了 直接return
    for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
      // 从第一个非叶子节点开始 一直到队首的节点
      this.bubbleDown(i) //bubbleDown操作  不断的向下移动 为什么叶子节点不用向下移动呢 因为叶子节点已经没有了下面的节点 不需要向下移动
    }
  }

  peek() {
    // 找到堆顶元素
    if (this.size() === 0) return null
    return this.data[0] //查看堆顶
  }

  offer(value) {
    // 向堆中加入元素
    this.data.push(value) //加入数组
    this.bubbleUp(this.size() - 1) // 调整加入的元素在小顶堆中的位置 这个函数会将传入的节点不断的向上移动 传入的是末尾的size-1
  }

  poll() {
    // 取出堆顶的元素
    if (this.size() === 0) {
      // 如果堆的大小是0 就没有元素 返回null 就行了
      return null
    }
    const result = this.data[0] // 拿到堆顶的元素
    const last = this.data.pop() // 拿到堆尾的元素
    if (this.size() !== 0) {
      // 如果节点的大小不是0 就进行节点的移动 使其符合定义
      this.data[0] = last //交换第一个元素和最后一个元素 将堆尾的元素插入变成第一个元素
      this.bubbleDown(0) //bubbleDown操作 然后进行下移重新排序
    }
    return result // 最后弹出堆顶的元素
  }

  bubbleUp(index) {
    // 传入当前的假如进来的节点的位置
    while (index > 0) {
      // 当位置大于0的时候不断的向上移动
      const parentIndex = (index - 1) >> 1 //父节点的位置
      //如果当前元素比父节点的元素小，就交换当前节点和父节点的位置
      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
        // 如果比较之后是小于0 就满足的构造器函数 需要进行交换 当前节点比父节点小就要交换
        // 如果是 b - a 的话 那就是大顶堆 就是当前节点比父节点大 那也要交换 所以只需要改构造器就行了
        this.swap(index, parentIndex) //交换自己和父节点的位置
        index = parentIndex //不断向上取父节点进行比较
      } else {
        break //如果当前元素比父节点的元素大，不需要处理
      }
    }
  }

  bubbleDown(index) {
    const lastIndex = this.size() - 1 //最后一个节点的位置
    while (true) {
      const leftIndex = index * 2 + 1 //左节点的位置
      const rightIndex = index * 2 + 2 //右节点的位置
      let findIndex = index //bubbleDown节点的位置 默认值是当前的索引
      //找出左右节点中value小的节点
      if (
        leftIndex <= lastIndex &&
        this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 // 如果左节点的索引小于最后一个节点的索引,并且 传入比较器之后呢,左边的位置的数字小于当前的位置的数字 就让当前的节点位置变成左节点的位置
      ) {
        findIndex = leftIndex
      }
      if (
        rightIndex <= lastIndex &&
        this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 // 右节点也是相同的道题
      ) {
        findIndex = rightIndex
      }
      if (index !== findIndex) {
        // 执行完上面的判断之后 如果index不是findIndex了说明左右节点有小于当前节点的值
        this.swap(index, findIndex) //交换当前元素和左右节点中value小的
        index = findIndex // 修改当前的index为记录的index 进行下一次循环
      } else {
        break // 如果这个index还是和findIndex相等了,那就没必要继续判断了 因为下面没有比他小的了 直接退出循环即可
      }
    }
  }

  swap(index1, index2) {
    //交换堆中两个元素的位置
    ;[this.data[index1], this.data[index2]] = [
      this.data[index2],
      this.data[index1],
    ]
  }

  size() {
    return this.data.length
  }
}
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (lists.length === 0) return null // 如果没有数据 就返回null
  let dummy = new ListNode(-1) // 虚拟头结点
  let p = dummy
  // 优先级队列,生成最小堆
  let pq = new Heap((a, b) => a.val - b.val)
  // 将k个链表的头结点加入到最小堆中
  for (let head of lists) {
    if (head !== null) {
      pq.offer(head)
    }
  }
  // 当堆不是空的
  while (pq.size() !== 0) {
    // 获取最小节点,接到结果链表中
    let node = pq.poll()
    p.next = node
    // 这个节点存在下一个节点
    if (node.next !== null) {
      pq.offer(node.next)
    }
    p = p.next
  }
  return dummy.next
}
